package com.wfm.tmp;

class P31下一个排列 {
    // 从右往左找到最小的i，从右往左找到比i大的j
    // 交换i，j
    // 再把 i后面的从小到大排序
    // 时O(N) 空O(1)
    public void nextPermutation(int[] nums){
        int i = nums.length-2;
        while (i>=0&&nums[i]>=nums[i+1]) i--;
        if(i>=0){
            int j =nums.length-1;
            while (j>=0&&nums[i]>=nums[j]) j--;
            swap(nums,i,j);
        }
        reserve(nums,i+1);
    }

    private void reserve(int[] nums, int i) {
        int left = i;
        int right = nums.length - 1;
        while (left<right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}